#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 狄克斯特拉算法(Dijkstra's algorithm)
# 狄克斯特拉算法用于在加权图中查找最短路径。
# 
# 有向加权图:
# A 为起点 , D 为终点
# A->B = 6 , A->C = 2 , C->B = 3 , B->D = 1 , C->D = 5
#
#     B
#   / |  \
# A   |    D
#   \ |  /
#     C
#

from collections import deque


start_node = 'A'
target_node = 'D'

# 生成图字典
graph = {}

graph['A'] = {}
graph['A']['B'] = 6
graph['A']['C'] = 2

graph['B'] = {}
graph['B']['D'] = 1

graph['C'] = {}
graph['C']['B'] = 3
graph['C']['D'] = 5

graph['D'] = {}

# 生成节点开销的散列表
infinity = float('inf')
costs = {}
costs['B'] = 6
costs['C'] = 2
costs['D'] = infinity

# 存储父节点的散列表
parents = {}
parents['B'] = 'A'
parents['C'] = 'A'
parents['D'] = None

processed = [] # 记录已处理过的节点

# 
def DJK_Search():
    node = find_lowest_cost_node(costs) # 在未处理的节点中找出开销最小的节点
    while node is not None:
        cost = costs[node] # 起点到当前节点的开销
        neighbors = graph[node] # 获取当前节点的邻居
        for n in neighbors.keys(): # 遍历当前节点的所有邻居
            new_cost = cost + neighbors[n] # 计算当前节点到邻居的开销
            if costs[n] > new_cost: # 如果从 起点 经 当前节点 到 邻居节点 开销比 直接从 起点 到 邻居节点 要快
                costs[n] = new_cost # 更新该邻居节点的开销
                parents[n] = node   # 更新该邻居节点的父节点为当前节点
        processed.append(node) # 标记当前节点已处理
        node = find_lowest_cost_node(costs) #寻找下一个未处理节点
    print(costs)
    print(parents)
    print_path()

# 查找开销最低的节点
def find_lowest_cost_node(costs):
    lowest_cost = float('inf')
    lowest_cost_node = None
    for node in costs: # 遍历所有节点
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

def print_path():
    path = deque() # 路径栈
    weight = deque() # 权重栈
    weight_sum = 0
    has_path = False
    node = target_node
    path.append(node)
    while True:
        parent_node = parents.get(node, None)
        if parent_node is None:
            break
        path.append(parent_node)
        weight.append(graph[parent_node][node])
        weight_sum += graph[parent_node][node]
        
        if parent_node == start_node:
            has_path = True
            break
        node = parent_node
            
    if has_path is True:
        for i in range(len(path)-1):
            print('%s --> ' % path.pop() , end='')
        print('%s' % path.pop())
        
        for i in range(len(weight)-1):
            print('%s + ' % weight.pop() , end='')
        print('%s = %d' % (weight.pop(), weight_sum))
    else:
        print('找不到从 %s 到 %s 的最短路径' % (start_node, target_node))
        

if __name__=='__main__':
    DJK_Search()
    
